Diameter of binary tree [DFS]

Time: O(N); Space: O(H); easy

Given a binary tree, you need to compute the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example 1:

    1
   / \
  2   3
 / \
4   5

Input: root = {TreeNode} [1,2,3,4,5]

Output: 3

Explanation:

• 3 is the length of the path [4,2,1,3] or [5,2,1,3]

Example 2:

    2
   /
  3
 /
1

Input: root = {TreeNode} [2,3,#,1]

Output: 2

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Depth-First Search

Intuition

Any path can be written as two arrows (in different directions) from some node, where an arrow is a path that starts at some node and only travels down to child nodes.

If we knew the maximum length arrows L, R for each child, then the best path touches L + R + 1 nodes.

Algorithm

Let’s calculate the depth of a node in the usual way: max(depth of node.left, depth of node.right) + 1.

While we do, a path “through” this node uses 1 + (depth of node.left) + (depth of node.right) nodes.

Let’s search each node and remember the highest number of nodes used in some path.

The desired length is 1 minus this number.

class Solution1(object):
    def diameterOfBinaryTree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def depth(root, diameter):
            if not root:
                return 0, diameter

            left, diameter = depth(root.left, diameter)
            right, diameter = depth(root.right, diameter)

            return 1 + max(left, right), max(diameter, 1 + left + right)

        return depth(root, 1)[1] - 1

s = Solution1()

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
assert s.diameterOfBinaryTree(root) == 3

root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(1)
assert s.diameterOfBinaryTree(root) == 2

See also:

https://leetcode.com/problems/diameter-of-binary-tree/

https://www.lintcode.com/problem/diameter-of-binary-tree